package cn.com.yang.datastruct.queue;

/**
 * 双端队列
 * @since 2023.07.22
 */
public class QueueTest2 {
    public static void main(String[] args) {

    }
}
class DoubleEndedQueue{
    // 存放数据的数组
    private Object[] elements; //初始长度16
    // 数组最大的长度
    private int maxSize;
    private int head;
    //尾部下标
    private int tail;
    public DoubleEndedQueue(){
        maxSize = 16;
        elements = new Object[16];
        head = 0;
        tail = 0;//双端队列只有在空队列的时候head==tail
    }
    // 取模运算，实现指针在数组中无限循环
    public int getMode(int index){
        if (index < 0){
            index = index + maxSize;
        }
        if (index >= maxSize){
            index = index - maxSize;
        }
        return index;
    }

    /**
     * 头部插入数据
     */
    public void addFirst(Object data){
        this.head =getMode(this.head-1);//头部指针向左移
//        head = (head-1) & (maxSize-1);
        elements[head]=data;
        if (head == tail){//队列满了，需要扩容操作，将长度 *2
            //expand();

        }
    }

    /**
     * 尾部插入数据
     * @param e
     */
    public void addLast(Object data){
        elements[tail] = data;
        this.tail = getMode(tail+1);//向右移动一位
        if (tail == head){
            //expand();//扩容
        }
    }
    /**
     * 实现头部移除
     */
    public Object removeFirst(){
        Object removeObj=null;
        if (head!=tail){
            removeObj  = elements[head];
            elements[head]= null;
            head = getMode(head+1);//将headhead指针向右移动一位
        }
        return removeObj;
    }

    /**
     * 尾部移除
     * @return
     */
    public Object removeLast(){
        Object removeObj = null;
        if (head!=tail){
            tail = getMode(tail-1);
            removeObj  =elements[tail];
            elements[tail]=null;
        }
        return removeObj;
    }
    //获取头部元素，不删除
    public Object peekFirst(){
        if (head!=tail){
            return elements[head];
        }else {
            return null;
        }
    }
    //获取尾部元素，不删除
    public Object peekLast(){
        if (head!=tail){
            return elements[tail-1];
        }else {
            return null;
        }
    }

    /**
     * 扩容
     */
    public void expand(){
        int newSize = maxSize << 1; //学习JDK源码写法
        Object[] newArr = new Object[newSize];
        //获取插入前的数据个数
        int n = maxSize-head;
        System.arraycopy(elements,head,newArr,0,n);
        System.arraycopy(elements,0,newArr,n,head);
        head=0;
        tail=maxSize;
        this.maxSize =newSize;
        this.elements=newArr;
    }
}